public class Solution483 {
    public long getFullOneNum(long mid,int len,long tar){
        long maxVal=tar/mid+1;
        long num=0;
        for (int i = 0; i < len; i++) {
            if(num>=maxVal){
                return tar+1;
            }
            num=mid*num+1;
        }
        return num;
    }

    public String smallestGoodBase(String n) {
        long result=Long.MAX_VALUE;
        long num=Long.valueOf(n);
        String strNum = Long.toBinaryString(num);
        for (int i = 1; i <=strNum.length() ; i++) {
            long left=2,right=num-1;
            while(left<=right) {
                long mid = left + (right - left) / 2;
                long tmpNum = getFullOneNum(mid, i,num);
                if(tmpNum==num){
                    result=Math.min(result,mid);
                    break;
                }
                else if(tmpNum>num){
                    right=mid-1;
                }
                else{
                    left=mid+1;
                }
            }
        }
        return String.valueOf(result);
    }

    public static void main(String[] args) {
        Solution483 s=new Solution483();
        System.out.println(s.smallestGoodBase("13"));
    }
}
